// AlExams.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <queue>
#include<bitset>
#include<set>
#include<queue>
#include<chrono>
#include<functional>

using namespace std;
using namespace chrono;

struct minTopcmp
{
	bool operator()(int a, int b)
	{
		return a > b;
	}
};
struct maxTopcmp
{
	bool operator()(int a, int b)
	{
		return a < b;
	}
};

int cmpfunc(const void * a, const void * b)
{
	return (*(int*)a - *(int*)b);
}

class NodeTree {
public:
	int content;
	NodeTree* left;
	NodeTree* right;
};

class ListNode {
public:
	int content;
	ListNode* next;
};

class Solution {
	
public:
	//机器人可到数
	int cnt = 0;

	map<char, bool> vowels;
	
	Solution()
	{
		vowels['a'] = true;
		vowels['e'] = true;
		vowels['i'] = true;
		vowels['o'] = true;
		vowels['u'] = true;
	}

	bool duplicate(int nums[], int lenght, int& out)
	{
		for (int i = 1; i <= lenght; ++i)
		{
			while (i != nums[i])
			{
				if (nums[i] == nums[nums[i]])
				{
					out = nums[i];
					return true;
				}
				swapElement(nums, i, nums[i]);
			}
		}
		return false;
	
	}

	void swapElement(int nums[], int i, int j)
	{
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	bool find(int target, int matrix[][100], int row, int col)
	{
		int rowIndex = 0;
		int colIndex = col - 1;
		while (rowIndex < row&&colIndex>0)
		{
			if (matrix[rowIndex][colIndex] < target)
			{
				++rowIndex;
			}
			else if (matrix[rowIndex][colIndex] > target)
			{
				--colIndex;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	int RectCover(int n)
	{
		if (n < 2)
		{
			return n;
		}
		int pre1 = 1;
		int pre2 = 2;
		int result = 3;
		for (int i = 2; i < n; ++i)
		{
			result = pre1 + pre2;
			pre1 = pre2;
			pre2 = result;
		}
		return result;
	}

	int JumpFloorII(int target)
	{
		int* dp= new int[target];
		for (int i = 0; i < target; ++i)
		{
			dp[i] = 1;
		}
		for (int i = 1; i < target; ++i)
		{
			for (int j = 0; j < i; ++j)
			{
				dp[i] +=dp[j];
			}
		}
		int result = dp[target - 1];
		delete[] dp;
		return result;
	}

	int numOfDigitSum(int num)
	{
		int sum = 0;
		while (num)
		{
			sum = sum + num % 10;
			num /= 10;
		}
		return sum;
	}

	void dfs( bool marked[][100], int k, int i, int j, int row, int col)
	{
		if (i < 0 || j < 0 || i == row - 1 || j == col - 1 || marked[i][j]) {
			return;
		}
		marked[i][j] = true;
		if (numOfDigitSum(i) + numOfDigitSum(j) > k)
			return;
		++cnt;
		int next[4][2] = { { 0,1 } ,{ 1,0 },{ -1,0 },{ 0,-1 } };
		for (int index = 0; index < 4; ++index)
		{
			dfs(marked, k, i + next[index][0], j + next[index][1], row, col);
		}
	}

	void robotMoveCount(int k, int  row, int col)
	{
		cnt = 0;
		bool marked[100][100];
		for (int i = 0; i < row; ++i)
		{
			for (int j = 0; j < col; ++j)
			{
				marked[i][j] = false;
			}
		}
		dfs(marked, k, 0, 0, row, col);
	}

	int cutTheRope(int n)
	{
		int* dp = new int[n];
		for (int i = 0; i < n; ++i)
		{
			dp[i] = 1;
		}
		for (int i = 2; i < n; ++i)
		{
			for (int j = 0; j < i; ++j)
			{
				dp[i] = max(dp[i], max(i*(i - j), dp[j] * (i - j)));
			}
		}
		int result = dp[n - 1];
		delete[] dp;
		return result;
	}

	int NumBitOf1(int n)
	{
		int cnt = 0;
		while (n)
		{
			cnt++;
			n &= n - 1;
		}
		return cnt;
	}

	int Power(double num, int exp)
	{
		if (exp == 0)
			return 1;
		if (exp == 1)
			return num;
		bool isnegative = false;
		if (exp < 0)
		{
			exp = -exp;
			isnegative = true;
		}

		int result = Power(num*num, exp / 2);
		
		if (exp % 2 != 0)
		{
			result = result*num;
		}
		
		return isnegative ? 1 / result : result;
	}

	void reOrderArray(int nums[], int len)
	{
		int* odd = new int[len];
		int* even = new int[len];

		int oddCount = 0;
		int evenCount = 0;
		for (int i = 0; i < len; ++i)
		{
			if (nums[i] % 2 == 0)
			{
				even[evenCount++] = nums[i];
			}
			else
			{
				odd[oddCount++] = nums[i];
			}
		}
		for (int i = 0; i < evenCount; ++i)
		{
			odd[oddCount + i] = even[i];
		}
		for (int i = 0; i < len; ++i)
		{
			nums[i] = odd[i];
		}
	}

	void printArray(int nums[], int len)
	{
		for (int i = 0; i < len; ++i)
		{
			cout << nums[i] << " ";
		}
		cout << endl;
	}

	ListNode* LinkListReberseK(ListNode* head,int k)
	{
		if (head == nullptr)
			return nullptr;
		ListNode* p1 = head;
		while (p1 != nullptr&&k-- > 0)
		{
			p1 = p1->next;
		}
		ListNode* p2 = head;
		while (p1 != nullptr)
		{
			p1 = p1->next;
			p2 = p2->next;
		}
		return p2;
	}

	ListNode* EntryNodeOfLoop(ListNode* head)
	{
		ListNode* slow = head;
		ListNode* fast = head;
		do
		{
			slow = slow->next;
			fast = fast->next->next;
		} while (slow != fast);
		fast = head;
		while (slow!=fast)
		{
			slow = slow->next;
			fast = fast->next;
		}
		return slow;
	}

	bool linkListHasCycle(ListNode* head)
	{
		ListNode* p1 = head;
		ListNode* p2 = head;

		while (p1 != nullptr&&p2 != nullptr&&p2->next != nullptr)
		{
			if (p1 == p2)
			{
				return true;
			}
			p1 = p1->next;
			p2 = p2->next->next;
		}

		return false;
	}

	tuple<int,int> twoSum(int nums[], int len, int target)
	{
		tuple<int, int> result;
		int left = 0, right = len - 1;
		int sum = 0;
		while (left < right)
		{
			sum = nums[left] + nums[right];
			if (sum < target)
			{
				++left;
			}
			else if (sum > target)
			{
				--right;
			}
			else
			{
				return tuple<int, int>(left + 1, right + 1);
			}
		}
		return tuple<int, int>(-1, -1);
	}

	bool judgeSequreSum(int n)
	{
		int left = 0, right = sqrt<int>(n);
		int sum = 0;
		while (left < right)
		{
			sum = left*left + right*right;
			if (sum == n)
			{
				return true;
			}
			else if (sum < n)
			{
				left++;
			}
			else
			{
				right++;
			}
		}
		return false;
	}

	void reverseVowels(char str[],int len)
	{
		int left = 0, right = len-1;

		while (left < right&&left < len && right>0)
		{
			while (vowels.find(str[left]) == vowels.end())
			{
				++left;
			}
			if (left > right || left > len || right < 0)
			{
				break;
			}
			while (vowels.find(str[right]) == vowels.end())
			{
				--right;
			}
			if (left > right || left > len || right < 0)
			{
				break;
			}
			char tmp = str[left];
			str[left++] = str[right];
			str[right--] = tmp;
		}
	}

	bool isSubStr(string str, string sub)
	{
		int i = 0, j = 0;
		
		int len1 = str.length(), len2 = sub.length();
		
		while (i < len1&&j < len2)
		{
			if (str[i] == sub[j])
			{
				++j;
			}
			++i;
		}
		return j == len2;
	}

	string longestSubWorlds(list<string> dict, string nstr)
	{
		string result;
		for (auto& value : dict)
		{
			if (isSubStr(nstr, value))
			{
				if (result.length() < value.length())
				{
					result = value;
				}
			}
		}
		return result;
	}

	void mergeSortArray(int nums1[], int m, int nums2[], int n)
	{
		int index1 = m - 1, index2 = n - 1;
		int indexMerge = m + n - 1;
		int* result = new int[m + n];
		while (index1 >= 0 || index2 >= 0)
		{
			if (nums1[index1] > nums2[index2])
			{
				result[indexMerge--] = nums1[index1--];
			}
			else if (nums1[index1] < nums2[index2])
			{
				result[indexMerge--] = nums2[index2--];
			}
			else if (index1 < 0)
			{
				result[indexMerge--] = nums2[index2--];
			}
			else if (index2 < 0)
			{
				result[indexMerge--] = nums1[index1--];
			}
		}
		for (int i = 0; i < m+n; ++i)
		{
			nums1[i] = result[i];
		}
		delete[] result;
	}

	int findMid(int a, int b, int c)
	{
		if (a >= b && b >= c || c >= b && b >= a)
			return b;
		else if (b >= a && a >= c || c >= a && a >= b)
			return a;
		else
			return c;
	}

	int selected(int nums[], int l, int r)
	{
		int i = l, j = r;
		int cardinal = findMid(nums[l], nums[r], nums[(l + r) / 2]);
		while (true)
		{
			while (nums[i] < cardinal && i < j)
			{
				++i;
			}
			while (nums[j] > cardinal && j > i)
			{
				--j;
			}
			if (i >= j)
			{
				break;
			}
			swapElement(nums, i, j);
		}
		return j;
	}

	int quickSelecet(int nums[],int len,int k)
	{
		int left = 0, right = len - 1;
		k = len - k;
		while (true)
		{
			int find = selected(nums, left, right);
			if (find == k)
			{
				return nums[k];
			}
			else if (find < k)
			{
				left = find + 1;
			}
			else if (find > k)
			{
				right = find - 1;
			}
		}
	}

	//查找出现频率最多的k和元素
	void findAppearKNum(int nums[], int len, int k)
	{
		partition(nums, nums + len, [&nums, this, &len](double d) {return d < findMid(nums[0], nums[len - 1], nums[len / 2]); });
		qsort(nums, len, sizeof(int), cmpfunc);
		printArray(nums, len);
		std::map<int, int> bulets;
		std::priority_queue<int, vector<int>, maxTopcmp> countSet;
		int count = 0;
		int preNum = nums[0];
		for (int i = 0; i < len; ++i)
		{
			if (nums[i] == preNum)
			{
				++count;
			}
			else
			{
				bulets[count] = preNum;
				countSet.push(count);
				count = 1;
			}
			preNum = nums[i];
		}
		
		count = 0;
		while (!countSet.empty())
		{
			int key = countSet.top();
			countSet.pop();
			cout << "count->key " << key << ":" << bulets[key] << endl;
		}
		//for (auto iter = countSet.rbegin(); iter != countSet.rend(); ++iter)
		//{
		//	if (count == k)
		//		break;
		//	cout << bulets[*iter] << " " << endl;
		//	++count;
		//}
		cout << endl;
	}
	
	//排序颜色
	void sortColors(int nums[], int len)
	{
		int colors[3] = { 0,0,0 };
		for (int i = 0; i < len; ++i)
		{
			++colors[nums[i]];
		}
		int index = 0;
		printArray(colors, 3);
		for (int i = 0; i < 3; ++i)
		{
			for (int j = 0; j < colors[i]; ++j)
			{
				nums[index++] = i;
			}
		}
		printArray(nums, len);
	}

	int distributionCookies(int childrens[], int len1, int cookies[], int len2)
	{
		qsort(childrens, len1, sizeof(int), cmpfunc);
		qsort(cookies, len2, sizeof(int), cmpfunc);

		int childCount = 0;
		int cookiCount = 0;
		while (childCount < len1&&cookiCount < len2)
		{
			if (childrens[childCount] <= cookies[cookiCount])
			{
				childCount++;
			}
			++cookiCount;
		}
		
		return childCount;
	}
};



int main()
{
	Solution so;
	int nums[6] = { 0,4,5,3,2,2 };
	int out;
	cout << "查找重复数字" << endl;
	cout << so.duplicate(nums, 5, out) << endl;
	cout << out << endl;

	cout << "递增矩阵查找数字" << endl;
	int mat[5][100] = {
		{1, 4, 7, 11, 15},
		{2, 5, 8, 12, 19},
		{3, 6, 9, 16, 22},
		{10, 13, 14, 17, 24},
		{18, 21, 23, 26, 30 }
	};
	cout << so.find(11, mat, 5, 5) << endl;
	cout << so.find(31, mat, 5, 5) << endl;

	cout << "我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？" << endl;
	cout << so.RectCover(3) << endl;
	cout << so.RectCover(4) << endl;
	

	cout << "一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法" << endl;
	cout << so.JumpFloorII(3) << endl;

	cout << "地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动，每一次只能向左右上下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为 18 时，机器人能够进入方格(35, 37)，因为 3 + 5 + 3 + 7 = 18。但是，它不能进入方格(35, 38)，因为 3 + 5 + 3 + 8 = 19。请问该机器人能够达到多少个格子？" << endl;
	so.robotMoveCount(18, 50, 50);
	cout << so.cnt << endl;

	cout << "输入一个整数，输出该数二进制表示中 1 的个数。" << endl;
	cout << so.NumBitOf1(10) << endl;
	cout << std::bitset<32>(10) << endl;

	cout << "给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent，求 base 的 exponent 次方。" << endl;
	cout << so.Power(3, 2) << endl;
	cout << so.Power(3, 3) << endl;

	cout << "调整数组顺序使奇数位于偶数前面。" << endl;
	int myarray[100] = { 1,2,3,4,5 };
	so.printArray(myarray, 5);
	so.reOrderArray(myarray, 5);
	so.printArray(myarray, 5);

	//cout << "设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。" << endl;
	//ListNode* head = new ListNode;
	//head->content = 1;
	//ListNode* node1 = new ListNode;
	//node1->content = 2;
	//head->next = node1;
	//ListNode* node2 = new ListNode;
	//node2->content = 3;
	//node1->next = node2;
	//ListNode* node3 = new ListNode;
	//node3->content = 4;
    //node2->next = node3;
	//ListNode* node4 = new ListNode;
	//node4->content = 5;
	//node3->next = node4;
	//ListNode* node5 = new ListNode;
	//node5->content = 6;
	//node4->next = node5;
	//ListNode* node6 = new ListNode;
	//node6->content = 7;
	//node5->next = node6;
	//node6->next = nullptr;
	//cout << so.LinkListReberseK(head, 4)->content << endl;

	cout << "一个链表中包含环，请找出该链表的环的入口结点。。" << endl;
	ListNode* head = new ListNode;
	head->content = 1;
	ListNode* node1 = new ListNode;
	node1->content = 2;
	head->next = node1;
	ListNode* node2 = new ListNode;
	node2->content = 3;
	node1->next = node2;
	ListNode* node3 = new ListNode;
	node3->content = 4;
	node2->next = node3;
	ListNode* node4 = new ListNode;
	node4->content = 5;
	node3->next = node4;
	ListNode* node5 = new ListNode;
	node5->content = 6;
	node4->next = node5;
	ListNode* node6 = new ListNode;
	node6->content = 7;
	node5->next = node6;
	node6->next = node3;
	cout << so.EntryNodeOfLoop(head)->content << endl;
	cout << " 判断链表是否存在环。。。。。" << endl;
	cout << so.linkListHasCycle(head) << endl;

	cout << "题目描述：在有序数组中找出两个数，使它们的和为 target。" << endl;
	int nums1[100] = { 1,2,3,4,5,6,7,8 };
	auto result = so.twoSum(nums1, 8, 10);
	cout << std::get<0>(result) << " " << std::get<1>(result) << endl;
	
	cout << "题目描述：判断一个数是否为两个数的平方和。" << endl;
	cout << so.judgeSequreSum(5) << endl;

	cout << "使用双指针指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历。" << endl;
	char str[] = ("leetcode");
	so.reverseVowels(str, 8);
	cout << str << endl;

	cout << "题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。" << endl;
	list<string> dict;
	dict.push_back("ale");
	dict.push_back("apple");
	dict.push_back("monkey");
	dict.push_back("plea");
	cout << so.longestSubWorlds(dict, "abpcplea") << endl;

	cout << "合并有序数组" << endl;
	int nums3[100] = { 1,3,5,6 };
	int nums4[100] = { 2,4,7,8 };
	so.mergeSortArray(nums3, 4, nums4, 4);
	so.printArray(nums3, 8);

	
	cout << "快速排序" << endl;
	int nums5[700] = { 65,999,89,2,677,3,4 };
	cout << so.quickSelecet(nums5, 7, 3) << endl;
	partition(nums5, nums5 + 7, [&nums5](double t) ->bool {return t > nums5[3]; });
	qsort(nums5,7, sizeof(int), cmpfunc);
	cout << nums5[7 - 3] << endl;

	cout << "大顶堆，小顶堆" << endl;

	priority_queue<int,vector<int>,maxTopcmp> maxTop;
	priority_queue<int, vector<int>, minTopcmp> minTop;
	for (int i = 0; i < 10; i++) {
		minTop.push(rand() % 20);
	}
	while (!minTop.empty()) {
		cout << minTop.top() << " ";
		minTop.pop();
	}
	cout << endl;

	cout << "集合 " << endl;
	struct cmpSet
	{
		bool operator()(int a, int b)
		{
			return a > b;
		}
	};
	set<int, cmpSet> s;
	s.insert({ 2,4,5,6,8,9,10,6 });
	
	for (auto iter = s.begin(); iter != s.end(); ++iter)
	{
		cout << *iter << " ";
	}
	cout << endl;

	cout << "查找出现次数最多的k个元素" << endl;
	int nums7[100] = { 1,2,3,1,1,1,2,3,3,3,3,2,2,2,4,4,4,5,6,6,7,3,3,3,2,2,4,5,6,7 };
	so.findAppearKNum(nums7, 30, 4);


	cout << "按颜色进行排序" << endl;
	int nums8[] = { 1,1,2,2,0,1,2,1,1,0,0,1,0 };
	so.printArray(nums8, 13);
	so.sortColors(nums8, 13);

	cout << "题目描述：每个孩子都有一个满足度，每个饼干都有一个大小，只有饼干的大小大于等于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。 " << endl;
	int nums9[] = { 1,2 };
	int nums10[] = { 1,2,3 };
	cout << so.distributionCookies(nums9, 2, nums10, 3) << endl;
	

	system("pause");
	
    return 0;
}

